import java.util.ArrayList;

public class MyLinkedList {
    //内部类定义节点
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val){
            this.val=val;
        }
    }
    //头节点
    public ListNode head;
    //尾节点
    public ListNode last;

    //头插方法
    public void addFirst(int data){
        ListNode listNode=new ListNode(data);
        //判断链表是否为空，为空则直接设置head与last
        if(head==null){
            head=last=listNode;
            return;
        }
        listNode.next=head;
        head.prev=listNode;
        head=listNode;
    }

    //尾插方法
    public void addLast(int data){
        ListNode listNode=new ListNode(data);
        //判断链表是否为空，为空则直接执行头插方法
        if(head==null){
            addFirst(data);
            return;
        }
        last.next=listNode;
        listNode.prev=last;
        last=listNode;
    }

    //底层方法，检查下标是否越界
    private void checkAddPos(int pos){
        if(pos<0||pos>getSize())
            throw new AddIndexPosIlegalException("双向链表插入位置不合法");
    }


    //底层方法，找到下标为pos的直接前驱节点
    private ListNode findIndex(int pos){
        ListNode cur=head;
        while(pos!=0){
            cur=cur.next;
            pos--;
        }
        return cur;
    }

    //在指定下标之前插入节点的方法
    public void addIndex(int data,int pos){
        //try,catch语句处理下标越界异常
        try{
            checkAddPos(pos);
        }catch (AddIndexPosIlegalException e){
            e.printStackTrace();
        }
        //判断是否为头插
        if(pos==0){
            addFirst(data);
            return;
        }
        //判断是否为尾插
        if(pos==getSize()){
            addLast(data);
            return;
        }
        //获取下标为pos的节点
        ListNode cur=findIndex(pos);
        ListNode listNode=new ListNode(data);
        //依次改变四个指针域
        listNode.next=cur;
        cur.prev.next=listNode;
        listNode.prev=cur.prev;
        cur.prev=listNode;
    }

    //删除第一个值为key的节点的方法
    public void toRemove(int key){
        //判断是否为空或单一节点链表
        if(head==last){
            head=last=null;
            return;
        }
        ListNode cur=head;
        while(cur!=null){
            if(cur.val==key){
                //判断是否为头节点
                if(cur==head){
                    head=head.next;
                    head.prev=null;
                    return;
                }
                //判断是否为尾节点
                if(cur==last){
                    last=last.prev;
                    last.next=null;
                    return;
                }
                //处理一般节点
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;
            }
            cur=cur.next;
        }
    }

    //删除所有值为key的节点的方法(同上即可)
    public void  removeAll(int key){

        ListNode cur=head;
        while(cur!=null){
            if(cur.val==key){
                if(head==last){
                    head=last=null;
                    break;
                }
                if(cur==head){
                    head=head.next;
                    head.prev=null;
                    break;
                }
                if(cur==last){
                    last=last.prev;
                    last.next=null;
                    break;
                }
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;
            }
            cur=cur.next;
        }
    }

    //在链表中查找是否包含值为key的节点的方法
    public boolean contains(int key){
        ListNode cur=head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    //获取链表的大小的方法
    public int getSize(){
        ListNode cur=head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }

    //打印整个链表的方法
    public void display(){
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    //清空整个链表的方法
    public void clear(){
        ListNode cur=head;
        ListNode suc=cur.next;
        while(suc!=null){
            cur=null;
            cur=suc;
            suc=suc.next;
        }
        cur=null;
        head=last=null;
    }
}


